package com.yuqingsong.algorithm;

import java.util.Arrays;

public class Sort {

	/**
	 * 插入排序
	 * @param array
	 * @return
	 */
	static int[] insertSort(int[] array){
		for(int i =1 ;i<array.length;i++){
			int current = array[i];
			int prev = i-1;
			for(;prev>=0&&array[prev]>current;prev--){
					//如果array[j]前一个元素大于current
				   //将array[j]到下一个位置
					array[prev+1] = array[prev];
			}
			//如果J元素比current值大，那么current就是元素的下一个元素
			array[prev+1] = current;
		}
		return array;
	}
	
	static int[] mergeSort(int[] array){
	   int mid = array.length/2;
		int[] left = new int[mid+(array.length%2==0?1:2)];
		int[] right = new int[mid+(array.length%2==0?1:2)];
		return mergeSort(array,0,array.length-1,left,right);
	}
	
	static int[] mergeSort(int[] array,int startIndex,int endIndex,int[] left,int[] right){
		if(startIndex<endIndex){
			int mid = (startIndex+endIndex)/2;
			mergeSort(array,startIndex,mid,left,right);
			mergeSort(array,mid+1,endIndex,left,right);
//			merge(array,startIndex,mid,endIndex,left,right);
			merge2(array,startIndex,mid,endIndex);
		}
		return array;
	}
	
	private static void merge(int[] array, int startIndex, int mid, int endIndex,int[] left,int[] right) {
			System.arraycopy(array, startIndex, left, 0, mid-startIndex+1);
			System.arraycopy(array, mid+1, right, 0, endIndex-mid);
			left[mid-startIndex+1]=Integer.MAX_VALUE;
			right[endIndex-mid]=Integer.MAX_VALUE;
			int l = 0,r = 0;
			for (int i = startIndex; i <= endIndex; i++) {
				if(left[l]<right[r]){
					array[i] = left[l++];
				}else{
					array[i] = right[r++];
				}
			}
	
	}
	private static void merge2(int[] array, int startIndex, int mid, int endIndex) {
		// arrayCopy 中的前一半保存left子数组,后一半保存right子数组
		int[] arrayCopy = new int[endIndex-startIndex+1];
		//复制array 的startIndex到endIndex(包含）到arrayCopy中
		System.arraycopy(array, startIndex, arrayCopy, 0, arrayCopy.length);
		int rStart = mid-startIndex+1;
		int l = 0,r = rStart;
		int left = arrayCopy[l];
		int right = arrayCopy[r];
		//对startIndex到endIndex中的所有元素进行排序
		for (int i = startIndex; i <= endIndex; i++) {
			//左右两边哪边的值小取哪边的值
			if(left<right){
				array[i] = left;
				if(++l<rStart){
					//左边的下一个值
					left = arrayCopy[l];
				}else{
					//左边的值已经取完，取最大值
					left = Integer.MAX_VALUE;
				}
			}else{
				array[i] = right;
				if(++r<arrayCopy.length){
					right = arrayCopy[r];
				}else{
					right = Integer.MAX_VALUE;
				}
			}
		}
		
	}
	

	public static void main(String[] args) {
		int count = 1000000;
//		int count = 3;
		int[] array = randomArray(count);
//		array = new int[]{7, 6, 5};
//		System.out.println(Arrays.toString(array));	
		long a = System.currentTimeMillis();
		int[] sortedArray ;
//		sortedArray = insertSort(array.clone());
		long b = System.currentTimeMillis();
//		System.out.println(Arrays.toString(sortedArray));	
		System.out.println(b-a);
		a = b;
		array = new int[]{1};
		
		sortedArray = mergeSort(array);
		b = System.currentTimeMillis();
		System.out.println(Arrays.toString(sortedArray));	
		System.out.println(b-a);
		a = b;
		
		int c = count*2;
		for(int i =0;i<c;i++){
			int[] array1 = (new int[1]);
		}
		b = System.currentTimeMillis();
		System.out.println(b-a);
		a = b;
	}

	public static int[] randomArray(int count) {
		int[] array = new int[count];
		for(int i = 0;i<array.length;i++){
			array[i] = (int)(Math.random()*10);
//			System.out.println(array[i]);
		}
		return array;
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	static int[] insert2(int array[]){
		for (int i = 0; i < array.length; i++) {
			int current = array[i];
			int j = i-1;
			for (; j >=0&& array[j]>current; j--) {
				array[j+1]=array[j];
			}
			array[j+1]=current;
		}
		return array;
	}
	
	
	
	
	
	
	
	
}
